import javafx.util.Pair;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        /**
         * 二叉树的最大宽度：
         * 解题思路：
         *  使用BFS遍历，对于每一层，使用两侧端点节点确定本层宽度（即需要给节点添加标签）
         * 额外标签：
         *  使用线性存储编号的方式，编号从1开始，假设根节点为x，则左子节点为2x，右子节点为2x+1
         * -- 这样的解题思路和并查集中给集合打标签的方法类似，通过给数据结构添加标签，使其能够表达更多信息 --
         * */
        // 1 预处理
        Deque<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 1));
        int maxLength = 1;
        // 2 BFS层序遍历，并更新最大宽度
        while(!queue.isEmpty()) {
            // -1 记录本层节点个数
            int n = queue.size();
            // -2 出本层节点
            for(int i = 0; i < n; i++) {
                Pair<TreeNode, Integer> cur = queue.poll();
                TreeNode curNode = cur.getKey();
                int curValue = cur.getValue();
                // -非空再入队
                if(curNode.left != null) {
                    queue.offer(new Pair<>(curNode.left, 2*curValue));
                }
                if(curNode.right != null) {
                    queue.offer(new Pair<>(curNode.right, 2*curValue+1));
                }
            }
            // -3 更新最大宽度
            if(!queue.isEmpty()) {
                maxLength = Math.max(maxLength, queue.peekLast().getValue() - queue.peekFirst().getValue() + 1);
            }
        }
        // 3 返回值
        return maxLength;
    }

    public List<Integer> largestValues(TreeNode root) {
        /**
         * 在每个树行中找最大值
         * 解题思路：
         *  分层BFS，每层结束后添加最大值*/
        // 1 预处理
        if(root == null) {
            return new LinkedList<>();
        }
        List<Integer> retArray = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        retArray.add(root.val);

        // 2 BFS层序遍历
        while(!queue.isEmpty()) {
            // -1 记录本层节点个数
            int n = queue.size();
            int maxValue = Integer.MIN_VALUE;

            // -2 出本层节点
            for(int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                if(cur.left != null) {
                    queue.offer(cur.left);
                    maxValue = Math.max(maxValue, cur.left.val);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                    maxValue = Math.max(maxValue, cur.right.val);
                }
            }

            // -3 整合数据
            // -本代码是在添加子节点时顺便计算最大值
            // -若此时为最后一层无子节点，此时队列为空，则不应该将未处理的maxValue整合
            if(!queue.isEmpty()) {
                retArray.add(maxValue);
            }
        }

        // 3 返回值
        return retArray;
    }
}
